<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="zh-Hans">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">






  
  
  <link rel="stylesheet" media="all" href="/blog/lib/Han/dist/han.min.css?v=3.3">




<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />















  
  
  <link href="/blog/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />




  
  
  
  

  
    
    
  

  

  

  

  

  
    
    
    <link href="//fonts.googleapis.com/css?family=Lato:300,300italic,400,400italic,700,700italic&subset=latin,latin-ext" rel="stylesheet" type="text/css">
  






<link href="/blog/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/blog/css/main.css?v=5.1.2" rel="stylesheet" type="text/css" />


  <meta name="keywords" content="数据结构,读书笔记," />








  <link rel="shortcut icon" type="image/x-icon" href="/blog/favicon.ico?v=5.1.2" />






<meta name="description" content="图的基本概念图的定义和术语一个图(G)定义为一个偶对(V,E) ，记为G=(V,E) 。其中： V是顶点(Vertex)的非空有限集合，记为V(G)；E是无序集V&amp;amp;V的一个子集，记为E(G) ，其元素是图的边(Edge)。将顶点集合为空的图称为空图。其形式化定义为：G=(V ，E)V={v|vÎdata object}E={| v,wÎV∧p(v,w)}P(v,w)表示从顶点v到顶点w有一">
<meta name="keywords" content="数据结构,读书笔记">
<meta property="og:type" content="article">
<meta property="og:title" content="图">
<meta property="og:url" content="https://git.oschina.net/choichumgming/blog/2017/12/25/图/index.html">
<meta property="og:site_name" content="choichumgming&#39;s blog">
<meta property="og:description" content="图的基本概念图的定义和术语一个图(G)定义为一个偶对(V,E) ，记为G=(V,E) 。其中： V是顶点(Vertex)的非空有限集合，记为V(G)；E是无序集V&amp;amp;V的一个子集，记为E(G) ，其元素是图的边(Edge)。将顶点集合为空的图称为空图。其形式化定义为：G=(V ，E)V={v|vÎdata object}E={| v,wÎV∧p(v,w)}P(v,w)表示从顶点v到顶点w有一">
<meta property="og:locale" content="zh-Hans">
<meta property="og:image" content="http://note.youdao.com/yws/res/1111/WEBRESOURCE40c69a8ef2a6176bf952274e6676bbe2">
<meta property="og:image" content="http://note.youdao.com/yws/res/1113/WEBRESOURCE965e8ca9569ef0e299c88220210e3c34">
<meta property="og:image" content="http://note.youdao.com/yws/res/1133/WEBRESOURCE5f09313ca32400f7ca0307e289753a70">
<meta property="og:image" content="http://note.youdao.com/yws/res/1153/WEBRESOURCE3d7d820762d0217278de5082e678075d">
<meta property="og:image" content="http://note.youdao.com/yws/res/1158/WEBRESOURCEf2336d12e4468d27bb15710809c4f7a0">
<meta property="og:image" content="http://note.youdao.com/yws/res/1402/WEBRESOURCEff37f8fc3caf57bbd159cba23b5fc09a">
<meta property="og:image" content="http://note.youdao.com/yws/res/1405/WEBRESOURCE90a6bb7a362c0b5320f02be0db19729d">
<meta property="og:updated_time" content="2018-01-08T05:13:10.853Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="图">
<meta name="twitter:description" content="图的基本概念图的定义和术语一个图(G)定义为一个偶对(V,E) ，记为G=(V,E) 。其中： V是顶点(Vertex)的非空有限集合，记为V(G)；E是无序集V&amp;amp;V的一个子集，记为E(G) ，其元素是图的边(Edge)。将顶点集合为空的图称为空图。其形式化定义为：G=(V ，E)V={v|vÎdata object}E={| v,wÎV∧p(v,w)}P(v,w)表示从顶点v到顶点w有一">
<meta name="twitter:image" content="http://note.youdao.com/yws/res/1111/WEBRESOURCE40c69a8ef2a6176bf952274e6676bbe2">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/blog/',
    scheme: 'Gemini',
    sidebar: {"position":"left","display":"post","offset":12,"offset_float":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: true,
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="https://git.oschina.net/choichumgming/blog/2017/12/25/图/"/>





  <title>图 | choichumgming's blog</title>
  








</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail ">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/blog/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">choichumgming's blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle">stay foolish,stay hard</p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/blog/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/blog/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/blog/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            归档
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/blog/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-commonweal">
          <a href="/blog/404.html" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-heartbeat"></i> <br />
            
            公益404
          </a>
        </li>
      
        
        <li class="menu-item menu-item-board">
          <a href="/blog/board/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-book"></i> <br />
            
            留言
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://git.oschina.net/choichumgming/blog/blog/2017/12/25/图/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="choichumgming">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/blog/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="choichumgming's blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">图</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-12-25T19:55:12+08:00">
                2017-12-25
              </time>
            

            

            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/blog/categories/算法与数据结构/" itemprop="url" rel="index">
                    <span itemprop="name">算法与数据结构</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/blog/2017/12/25/图/#SOHUCS" itemprop="discussionUrl">
                  <span id="changyan_count_unit" class="post-comments-count hc-comment-count" data-xid="2017/12/25/图/" itemprop="commentsCount"></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        <h2 id="图的基本概念"><a href="#图的基本概念" class="headerlink" title="图的基本概念"></a>图的基本概念</h2><h3 id="图的定义和术语"><a href="#图的定义和术语" class="headerlink" title="图的定义和术语"></a>图的定义和术语</h3><p>一个图(G)定义为一个偶对(V,E) ，记为G=(V,E) 。其中： V是顶点(Vertex)的非空有限集合，记为V(G)；E是无序集V&amp;V的一个子集，记为E(G) ，其元素是图的边(Edge)。<br>将顶点集合为空的图称为空图。其形式化定义为：<br>G=(V ，E)<br>V={v|vÎdata object}<br>E={<v,w>| v,wÎV∧p(v,w)}<br>P(v,w)表示从顶点v到顶点w有一条直接通路</v,w></p>
<h3 id="完全无向图"><a href="#完全无向图" class="headerlink" title="完全无向图"></a>完全无向图</h3><p>对于无向图，若图中顶点数为n ，用e表示边的数目，则e Î[0，n(n-1)/2] 。具有n(n-1)/2条边的无向图称为完全无向图。<br>完全无向图另外的定义是：</p>
<ul>
<li>对于无向图G=(V，E)，若”vi，vj ÎV ，当vi≠vj时，有(vi ,vj)ÎE，图中任意两个不同的顶点间都有一条无向边，这样的无向图称为完全无向图</li>
<li><strong>子图和生成子图</strong>：设有图G=(V，E)和G’=(V’，E’)，若V’ÌV且E’ÌE ，则称图G’是G的子图；若V’=V且E’C=E，则称图G’是G的一个生成子图。</li>
<li><strong>顶点的邻接(Adjacent)</strong>：对于无向图G=(V，E)，若边(v,w)ÎE，则称顶点v和w 互为邻接点，即v和w相邻接。边(v,w)依附(incident)与顶点v和w 。</li>
<li>对于<strong>有向图G=(V ，E)</strong>，若有向弧<v,w>ÎE，则称顶点v “<strong>邻接到</strong>”顶点w，顶点w “邻接自”顶点v ，弧<v,w> 与顶点v和w “相关联” 。</v,w></v,w></li>
<li><strong>顶点的度、入度、出度</strong>：对于无向图G=(V，E)， “viÎV，图G中依附于vi的边的数目称为顶点vi的度(degree)，记为TD(vi)。</li>
</ul>
<h3 id="邻接链表法"><a href="#邻接链表法" class="headerlink" title="邻接链表法"></a>邻接链表法</h3><p>基本思想<br>对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。第i个单链表表示依附于顶点Vi的边(对有向图是以顶点Vi为头或尾的弧)。<br><img src="http://note.youdao.com/yws/res/1111/WEBRESOURCE40c69a8ef2a6176bf952274e6676bbe2" alt="Alt text"><br><img src="http://note.youdao.com/yws/res/1113/WEBRESOURCE965e8ca9569ef0e299c88220210e3c34" alt="Alt text"><br><strong>邻接表法的特点</strong></p>
<ul>
<li>表头向量中每个分量就是一个单链表的头结点，分量个数就是图中的顶点数目；</li>
<li>在边或弧稀疏的条件下，用邻接表表示比用邻接矩阵表示节省存储空间；</li>
<li>在无向图，顶点Vi的度是第i个链表的结点数；</li>
<li>对有向图可以建立正邻接表或逆邻接表。正邻接表是以顶点Vi为出度(即为弧的起点)而建立的邻接表；逆邻接表是以顶点Vi为入度(即为弧的终点)而建立的邻接表；</li>
<li>在有向图中，第i个链表中的结点数是顶点Vi的出 (或入)度；求入 (或出)度，须遍历整个邻接表；</li>
<li>在邻接表上容易找出任一顶点的第一个邻接点和下一个邻接点；<br>结点及其类型定义</li>
</ul>
<h2 id="图的连通性问题"><a href="#图的连通性问题" class="headerlink" title="图的连通性问题"></a>图的连通性问题</h2><h3 id="无向图的连通分量和生成树"><a href="#无向图的连通分量和生成树" class="headerlink" title="无向图的连通分量和生成树"></a>无向图的连通分量和生成树</h3><p>对于无向图，对其进行遍历时：</p>
<ul>
<li>若是连通图：仅需从图中任一顶点出发，就能访问图中的所有顶点；</li>
<li>若是非连通图：需从图中多个顶点出发。每次从一个新顶点出发所访问的顶点集序列恰好是各个连通分量的顶点集；<br><img src="http://note.youdao.com/yws/res/1133/WEBRESOURCE5f09313ca32400f7ca0307e289753a70" alt="Alt text"></li>
</ul>
<p>若G=(V,E)是<strong>无向连通图</strong>， 顶点集和边集分别是V(G) ，E(G) 。若从G中任意点出发遍历时， E(G)被<strong>分成两个互不相交的集合</strong>：<br>T(G) ：遍历过程中<strong>所经过的边</strong>的集合；<br>B(G) ：遍历过程中<strong>未经过的边</strong>的集合；<br>显然： <strong>E(G)=T(G)∪B(G) ，T(G)∩B(G)=Ø</strong><br> 显然，图G’=(V, T(G))是G的极小连通子图，且G’是一棵树。G’称为图G的一棵<strong>生成树</strong>。<br>从任意点出发按DFS算法得到生成树G’称为深度优先生成树；按BFS算法得到的G’称为广度优先生成树。</p>
<p>若G=(V,E)是<strong>无向非连通图</strong>，对图进行遍历时得到若干个连通分量的顶点集：V1(G) ,V2(G) ,…,Vn(G)和相应所经过的边集：T1(G) ,T2(G) , …,Tn(G) 。<br>则对应的顶点集和边集的二元组：Gi=(Vi(G),Ti(G))(1≦i≦n)是对应分量的生成树，所有这些生成树构成了原来非连通图的生成森林。</p>
<p><strong>说明：当给定无向图要求画出其对应的生成树或生成森林时，必须先给出相应的邻接表，然后才能根据邻接表画出其对应的生成树或生成森林。</strong></p>
<h3 id="最小生成树"><a href="#最小生成树" class="headerlink" title="最小生成树"></a>最小生成树</h3><p>如果连通图是一个<strong>带权图</strong>，则其生成树中的边也带权，生成树中<strong>所有边的权值之和</strong>称为<strong>生成树的代价。</strong><br><strong>最小生成树(Minimum Spanning Tree) ：带权连通图中代价最小的生成树称为最小生成树。</strong><br>构造最小生成树的算法有许多，基本原则是：</p>
<ul>
<li>尽可能选取权值最小的边，但不能构成回路；</li>
<li>选择n-1条边构成最小生成树。<br>以上的基本原则是<strong>基于MST</strong>的如下性质：<pre><code>设G=(V，E)是一个带权连通图，U是顶点集V的一个非空子集。若u∈U ，v∈V-U，且(u, v)是U中顶点到V-U中顶点之间权值最小的边，则必存在一棵包含边(u, v)的最小生成树。
</code></pre><h4 id="普里姆-Prim-算法"><a href="#普里姆-Prim-算法" class="headerlink" title="普里姆(Prim)算法"></a>普里姆(Prim)算法</h4>从连通网N=(U，E)中找最小生成树T=(U，TE) 。<br><strong>算法思想:</strong><br>⑴  若从顶点v0出发构造，U={v0}，TE={}；<br>⑵ 先找权值最小的边(u，v)，其中u∈U且v∈V-U，则U= U∪{v}，TE=TE∪{(u，v)} ；<br>⑶ 重复⑵ ，直到U=V为止。则TE中必有n-1条边， T=(U，TE)就是最小生成树。<br><img src="http://note.youdao.com/yws/res/1153/WEBRESOURCE3d7d820762d0217278de5082e678075d" alt="Alt text"><blockquote>
<p>简而言之就是：<br>任意找一个点，找与他相连它权重最小的边，<br>将这条边的邻接点加入节点数组中<br>再从节点数组中，选出与这些顶点相连，权重最小的边（成环的情况要考虑）<br>要判断该条边的两个节点是否同时已经加入到节点数组中<br>如果是，则忽略这条边<br>如果不是，选择这条边，并将这个新节点加入节点数组中</p>
</blockquote>
</li>
</ul>
<p>以下是用prim算法求MST<br><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div><div class="line">73</div><div class="line">74</div><div class="line">75</div><div class="line">76</div><div class="line">77</div><div class="line">78</div><div class="line">79</div><div class="line">80</div><div class="line">81</div><div class="line">82</div><div class="line">83</div><div class="line">84</div><div class="line">85</div><div class="line">86</div><div class="line">87</div><div class="line">88</div><div class="line">89</div><div class="line">90</div><div class="line">91</div><div class="line">92</div><div class="line">93</div><div class="line">94</div><div class="line">95</div><div class="line">96</div><div class="line">97</div><div class="line">98</div><div class="line">99</div><div class="line">100</div><div class="line">101</div><div class="line">102</div><div class="line">103</div><div class="line">104</div><div class="line">105</div><div class="line">106</div><div class="line">107</div><div class="line">108</div><div class="line">109</div><div class="line">110</div><div class="line">111</div><div class="line">112</div><div class="line">113</div><div class="line">114</div><div class="line">115</div><div class="line">116</div><div class="line">117</div><div class="line">118</div><div class="line">119</div><div class="line">120</div><div class="line">121</div><div class="line">122</div><div class="line">123</div><div class="line">124</div><div class="line">125</div><div class="line">126</div><div class="line">127</div><div class="line">128</div><div class="line">129</div><div class="line">130</div><div class="line">131</div><div class="line">132</div><div class="line">133</div><div class="line">134</div><div class="line">135</div><div class="line">136</div><div class="line">137</div><div class="line">138</div><div class="line">139</div><div class="line">140</div><div class="line">141</div><div class="line">142</div><div class="line">143</div><div class="line">144</div><div class="line">145</div><div class="line">146</div><div class="line">147</div><div class="line">148</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">package</span> ACM;</div><div class="line"></div><div class="line"><span class="keyword">import</span> java.util.ArrayList;</div><div class="line"><span class="keyword">import</span> java.util.Scanner;</div><div class="line"><span class="comment">/*</span></div><div class="line"><span class="comment"> * prim算法求最小生成树</span></div><div class="line"><span class="comment"> */</span></div><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Main</span> </span>&#123;</div><div class="line">    <span class="keyword">private</span> VNode[] mVexs;  <span class="comment">// 顶点数组</span></div><div class="line">    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">int</span> INF = Integer.MAX_VALUE;</div><div class="line">    <span class="keyword">int</span> vertex,edges;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Main</span><span class="params">()</span> </span>&#123;</div><div class="line">        Scanner sc=<span class="keyword">new</span> Scanner(System.in);</div><div class="line">        vertex=sc.nextInt();edges=sc.nextInt();</div><div class="line">        mVexs=<span class="keyword">new</span> VNode[vertex];</div><div class="line">        </div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; vertex;i++) &#123;</div><div class="line">            mVexs[i] = <span class="keyword">new</span> VNode();</div><div class="line">            mVexs[i].data =i; mVexs[i].firstEdge = <span class="keyword">null</span>;</div><div class="line">        &#125;</div><div class="line">        </div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; edges;i++) &#123;</div><div class="line">            <span class="comment">// 读取边的起始顶点和结束顶点、权重</span></div><div class="line">            <span class="keyword">int</span> p1=sc.nextInt();</div><div class="line">            <span class="keyword">int</span> p2=sc.nextInt();</div><div class="line">            <span class="keyword">int</span> weight=sc.nextInt();</div><div class="line">            createGragh(p1, p2,weight);</div><div class="line">            </div><div class="line">        &#125;</div><div class="line">        System.out.print(prim(<span class="number">0</span>));</div><div class="line">    &#125;</div><div class="line">    </div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">createGragh</span><span class="params">(<span class="keyword">int</span> p1,<span class="keyword">int</span> p2,<span class="keyword">int</span> weight)</span> </span>&#123;<span class="comment">//创建表</span></div><div class="line">         </div><div class="line">        ENode node=<span class="keyword">new</span> ENode();</div><div class="line">        node.ivex=p2;</div><div class="line">        node.weight=weight;</div><div class="line">        <span class="keyword">if</span> ((mVexs[p1].firstEdge == <span class="keyword">null</span>))</div><div class="line">                mVexs[p1].firstEdge = node;</div><div class="line">              <span class="keyword">else</span></div><div class="line">                  linkLast(mVexs[p1].firstEdge, node);<span class="comment">// 将node链接到"p1所在链表的末尾"</span></div><div class="line">       </div><div class="line">        node=<span class="keyword">new</span> ENode();</div><div class="line">        node.ivex=p1;</div><div class="line">        node.weight=weight;</div><div class="line">        <span class="keyword">if</span> ((mVexs[p2].firstEdge == <span class="keyword">null</span>))</div><div class="line">                mVexs[p2].firstEdge = node;</div><div class="line">              <span class="keyword">else</span></div><div class="line">                  linkLast(mVexs[p2].firstEdge, node);<span class="comment">// 将node链接到"p2所在链表的末尾"</span></div><div class="line">        </div><div class="line">    &#125;</div><div class="line">    </div><div class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">linkLast</span><span class="params">(ENode list, ENode node)</span> </span>&#123;</div><div class="line">        ENode p = list;</div><div class="line"></div><div class="line">        <span class="keyword">while</span>(p.nextEdge!=<span class="keyword">null</span>)</div><div class="line">            p = p.nextEdge;</div><div class="line">        p.nextEdge = node;</div><div class="line">    &#125;</div><div class="line">  </div><div class="line">    <span class="comment">/*</span></div><div class="line"><span class="comment">     * 获取边&lt;start, end&gt;的权值；若start和end不是连通的，则返回无穷大。</span></div><div class="line"><span class="comment">     */</span></div><div class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">getWeight</span><span class="params">(<span class="keyword">int</span> start, <span class="keyword">int</span> end)</span> </span>&#123;</div><div class="line"></div><div class="line">        <span class="keyword">if</span> (start==end)</div><div class="line">            <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line"></div><div class="line">        ENode node = mVexs[start].firstEdge;</div><div class="line">        <span class="keyword">while</span> (node!=<span class="keyword">null</span>) &#123;</div><div class="line">            <span class="keyword">if</span> (end==node.ivex)</div><div class="line">                <span class="keyword">return</span> node.weight;</div><div class="line">            node = node.nextEdge;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="keyword">return</span> INF;<span class="comment">//若start和end不是连通的，则返回无穷大。</span></div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">int</span> <span class="title">prim</span><span class="params">(<span class="keyword">int</span> start)</span></span>&#123;</div><div class="line">        </div><div class="line">        <span class="keyword">int</span> num =vertex;</div><div class="line">        <span class="keyword">int</span> index=<span class="number">0</span>;                   <span class="comment">// prim最小树的索引，即prims数组的索引</span></div><div class="line">        <span class="keyword">int</span>[] prims = <span class="keyword">new</span> <span class="keyword">int</span>[num];  <span class="comment">// prim最小树的结果数组</span></div><div class="line">        <span class="keyword">int</span>[] weights = <span class="keyword">new</span> <span class="keyword">int</span>[num];  <span class="comment">// 顶点间边的权值</span></div><div class="line"></div><div class="line">        <span class="comment">// prim最小生成树中第一个数是"图中第start个顶点"，因为是从start开始的。</span></div><div class="line">        prims[index++] = mVexs[start].data;</div><div class="line">        </div><div class="line">        <span class="comment">// 初始化"顶点的权值数组"，</span></div><div class="line">        <span class="comment">// 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。</span></div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; num; i++ )</div><div class="line">            weights[i] = getWeight(start, i);</div><div class="line">        </div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; vertex; i++) &#123;</div><div class="line">            <span class="comment">// 由于从start开始的，因此不需要再对第start个顶点进行处理。</span></div><div class="line">            <span class="keyword">if</span>(start == i)</div><div class="line">                <span class="keyword">continue</span>;</div><div class="line"></div><div class="line">            <span class="keyword">int</span> j = <span class="number">0</span>,min = INF,k = <span class="number">0</span>;</div><div class="line">           </div><div class="line">            </div><div class="line">            <span class="comment">// 在未被加入到最小生成树的顶点中，找出权值最小的顶点。</span></div><div class="line">            <span class="keyword">while</span> (j &lt; num) &#123;</div><div class="line">                <span class="comment">// 若weights[j]=0，意味着"第j个节点已经被排序过"(或者说已经加入了最小生成树中)。</span></div><div class="line">                <span class="keyword">if</span> (!mVexs[j].mark&amp;&amp; weights[j] &lt; min) &#123;</div><div class="line">                    min = weights[j];</div><div class="line">                    k = j;</div><div class="line">                &#125;</div><div class="line">                j++;</div><div class="line">            &#125;</div><div class="line">            </div><div class="line">            <span class="comment">// 经过上面的处理后，在未被加入到最小生成树的顶点中，权值最小的顶点是第k个顶点。</span></div><div class="line">            <span class="comment">// 将第k个顶点加入到最小生成树的结果数组中</span></div><div class="line">            prims[index++] = mVexs[k].data;</div><div class="line">            </div><div class="line">            <span class="comment">// 将"第k个顶点的权值"标记为0，意味着第k个顶点已经排序过了(或者说已经加入了最小树结果中)。</span></div><div class="line">            mVexs[k].mark=<span class="keyword">true</span>;</div><div class="line">            </div><div class="line">            <span class="comment">// 当第k个顶点被加入到最小生成树的结果数组中之后，更新其它顶点的权值。</span></div><div class="line">            <span class="keyword">for</span> (j = <span class="number">0</span> ; j &lt; vertex; j++) &#123;</div><div class="line">                <span class="comment">// 获取第k个顶点到第j个顶点的权值</span></div><div class="line">                <span class="keyword">int</span> tmp = getWeight(k, j);</div><div class="line">                <span class="comment">// 当第j个节点没有被处理，并且需要更新时才被更新。</span></div><div class="line">                <span class="keyword">if</span> (!mVexs[j].mark &amp;&amp; tmp &lt; weights[j])</div><div class="line">                    weights[j] = tmp;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">        </div><div class="line">        <span class="keyword">int</span> ans=<span class="number">0</span>;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;index;i++)ans+=weights[i];</div><div class="line">        <span class="keyword">return</span> ans;</div><div class="line">    &#125;</div><div class="line">    </div><div class="line">    <span class="comment">// 邻接表中表的顶点</span></div><div class="line">    <span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">VNode</span> </span>&#123;</div><div class="line">        <span class="keyword">int</span> data;          <span class="comment">// 顶点信息</span></div><div class="line">        ENode firstEdge;    <span class="comment">// 指向第一条依附该顶点的弧</span></div><div class="line">        <span class="keyword">boolean</span> mark=<span class="keyword">false</span>;</div><div class="line">    &#125;</div><div class="line">    </div><div class="line">     <span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">ENode</span> </span>&#123;</div><div class="line">            <span class="keyword">int</span> ivex;       <span class="comment">// 该边所指向的顶点的位置</span></div><div class="line">            <span class="keyword">int</span> weight;     <span class="comment">// 该边的权</span></div><div class="line">            ENode nextEdge; <span class="comment">// 指向下一条弧的指针</span></div><div class="line">    &#125;</div><div class="line">     <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</div><div class="line">        Main prim= <span class="keyword">new</span> Main();</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>
<h3 id="克鲁斯卡尔-Kruskal-算法"><a href="#克鲁斯卡尔-Kruskal-算法" class="headerlink" title="克鲁斯卡尔(Kruskal)算法"></a>克鲁斯卡尔(Kruskal)算法</h3><p><strong>算法思想</strong><br>        设G=(V, E)是具有n个顶点的连通网，T=(U, TE)是其最小生成树。初值：U=V，TE={} 。<br>对G中的边按权值大小从小到大依次选取。<br>⑴   选取权值最小的边(vi，vj)，若边(vi，vj)加入到TE后形成回路，则舍弃该边(边(vi，vj) ；否则，将该边并入到TE中，即TE=TE∪{(vi，vj)} 。<br>⑵ 重复⑴ ，直到TE中包含有n-1条边为止。<br><img src="http://note.youdao.com/yws/res/1158/WEBRESOURCEf2336d12e4468d27bb15710809c4f7a0" alt="Alt text"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div><div class="line">73</div><div class="line">74</div><div class="line">75</div><div class="line">76</div><div class="line">77</div><div class="line">78</div><div class="line">79</div><div class="line">80</div><div class="line">81</div><div class="line">82</div><div class="line">83</div><div class="line">84</div><div class="line">85</div><div class="line">86</div><div class="line">87</div><div class="line">88</div><div class="line">89</div><div class="line">90</div><div class="line">91</div><div class="line">92</div><div class="line">93</div><div class="line">94</div><div class="line">95</div><div class="line">96</div><div class="line">97</div><div class="line">98</div><div class="line">99</div><div class="line">100</div><div class="line">101</div><div class="line">102</div><div class="line">103</div><div class="line">104</div><div class="line">105</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">package</span> ACM;</div><div class="line"></div><div class="line"><span class="keyword">import</span> java.lang.reflect.Array;</div><div class="line"><span class="keyword">import</span> java.util.Arrays;</div><div class="line"><span class="keyword">import</span> java.util.Comparator;</div><div class="line"><span class="keyword">import</span> java.util.Scanner;</div><div class="line"><span class="comment">/*</span></div><div class="line"><span class="comment">|Kruskal算法|</span></div><div class="line"><span class="comment">|适用于 稀疏图 求最小生成树|</span></div><div class="line"><span class="comment"></span></div><div class="line"><span class="comment">*/</span></div><div class="line"></div><div class="line"><span class="comment">/*</span></div><div class="line"><span class="comment">第一步：点、边、加入vector，把所有边按从小到大排序</span></div><div class="line"><span class="comment">第二步：并查集部分 + 下面的code</span></div><div class="line"><span class="comment">*/</span></div><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Kruskal1</span> </span>&#123;</div><div class="line">    <span class="keyword">private</span>  edges[] id;</div><div class="line">    <span class="keyword">private</span>  <span class="keyword">int</span>[] sz,node;</div><div class="line">    <span class="keyword">int</span> ver,edge,ans;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Kruskal1</span><span class="params">()</span></span>&#123;</div><div class="line">        Scanner sc=<span class="keyword">new</span> Scanner(System.in);</div><div class="line">        ver=sc.nextInt();</div><div class="line">        edge=sc.nextInt();</div><div class="line">        </div><div class="line">        id=<span class="keyword">new</span> edges[edge];</div><div class="line">        sz=<span class="keyword">new</span> <span class="keyword">int</span>[ver];</div><div class="line">        node=<span class="keyword">new</span> <span class="keyword">int</span>[ver];</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;edge;i++)&#123;</div><div class="line">            id[i]=<span class="keyword">new</span> edges();</div><div class="line">            id[i].u=sc.nextInt();id[i].v=sc.nextInt();id[i].weight=sc.nextInt();</div><div class="line">            </div><div class="line">        &#125;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;ver;i++)&#123;</div><div class="line">            sz[i]=<span class="number">1</span>;node[i]=i;</div><div class="line">        &#125;</div><div class="line">        Arrays.sort(id,<span class="keyword">new</span> cmp());</div><div class="line">        kruskal();</div><div class="line">        System.out.print(ans);</div><div class="line">    &#125;</div><div class="line">    </div><div class="line">    </div><div class="line">    <span class="class"><span class="keyword">class</span> <span class="title">cmp</span> <span class="keyword">implements</span> <span class="title">Comparator</span>&lt;<span class="title">edges</span>&gt;</span>&#123;</div><div class="line">        <span class="meta">@Override</span></div><div class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">compare</span><span class="params">(edges o1, edges o2)</span> </span>&#123;</div><div class="line">            <span class="comment">// TODO Auto-generated method stub</span></div><div class="line">            </div><div class="line">            <span class="keyword">return</span> (o1.weight&gt;o2.weight)?<span class="number">1</span>:-<span class="number">1</span>;</div><div class="line">        &#125;</div><div class="line">        </div><div class="line">    &#125;</div><div class="line">    </div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">connected</span><span class="params">(<span class="keyword">int</span> p, <span class="keyword">int</span> q)</span> </span>&#123;</div><div class="line">          <span class="keyword">return</span> find(p) == find(q);</div><div class="line">    &#125;  </div><div class="line">       </div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> p)</span> </span>&#123;</div><div class="line">        <span class="comment">// 寻找p节点所在组的根节点，根节点具有性质id[root] = root  </span></div><div class="line">         <span class="keyword">while</span> (p != node[p])  </div><div class="line">            &#123;  </div><div class="line">                <span class="comment">// 将p节点的父节点设置为它的爷爷节点  </span></div><div class="line">             node[p] = node[node[p]];  </div><div class="line">                p = node[p];  </div><div class="line">            &#125;  </div><div class="line">        <span class="keyword">return</span> p;  </div><div class="line">    &#125;</div><div class="line">    </div><div class="line">    </div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span>  <span class="title">kruskal</span><span class="params">()</span> </span>&#123;</div><div class="line">           ans = <span class="number">0</span>;</div><div class="line">           <span class="keyword">int</span> len=ver;</div><div class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i&lt;edge; i++) &#123;  </div><div class="line">                <span class="keyword">if</span>(len==<span class="number">0</span>)<span class="keyword">break</span>;</div><div class="line">                <span class="keyword">if</span> (find(id[i].u) != find(id[i].v)) &#123;    </div><div class="line">                    union(id[i].u, id[i].v);    </div><div class="line">                    ans += id[i].weight;</div><div class="line"><span class="comment">//                  System.out.println(id[i].u+" "+id[i].v+" "+id[i].weight+" ");</span></div><div class="line">                    len--;</div><div class="line">                &#125;    </div><div class="line">            &#125; </div><div class="line">    &#125;</div><div class="line">    </div><div class="line">    <span class="class"><span class="keyword">class</span> <span class="title">edges</span></span>&#123;</div><div class="line">        <span class="keyword">int</span> u,v;</div><div class="line">        <span class="keyword">int</span> weight; </div><div class="line">    &#125;</div><div class="line">    </div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">union</span><span class="params">(<span class="keyword">int</span> p, <span class="keyword">int</span> q)</span> </span>&#123;</div><div class="line">         <span class="comment">// 获得p和q的组号  </span></div><div class="line">         <span class="keyword">int</span> pRoot = find(p);  </div><div class="line">         <span class="keyword">int</span> qRoot = find(q);  </div><div class="line">         <span class="keyword">if</span> (pRoot == qRoot) <span class="keyword">return</span>;  </div><div class="line">         <span class="keyword">if</span>(sz[qRoot]&gt;sz[pRoot])&#123; <span class="comment">// 将一颗树(即一个组)变成另外一课树(即一个组)的子树 ,将小树作为大树的子树  </span></div><div class="line">             node[pRoot]=qRoot;</div><div class="line">            sz[pRoot]+=sz[qRoot];</div><div class="line">         &#125;<span class="keyword">else</span>&#123;</div><div class="line">             node[qRoot]=pRoot;</div><div class="line">                sz[qRoot]+=sz[pRoot];</div><div class="line">         &#125;</div><div class="line">         </div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</div><div class="line">        </div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h3 id="最短路径"><a href="#最短路径" class="headerlink" title="最短路径"></a>最短路径</h3><p>若用带权图表示交通网，图中顶点表示地点，边代表两地之间有直接道路，边上的权值表示路程(或所花费用或时间) 。从一个地方到另一个地方的路径长度表示该路径上各边的权值之和。问题：</p>
<ul>
<li>两地之间是否有通路?</li>
<li>在有多条通路的情况下，哪条最短?<blockquote>
<p>考虑到交通网的有向性，直接讨论的是带权有向图的最短路径问题，但解决问题的算法也适用于无向图。<br>将一个路径的起始顶点称为源点，最后一个顶点称为终点。</p>
</blockquote>
</li>
</ul>
<h4 id="单源点最短路径"><a href="#单源点最短路径" class="headerlink" title="单源点最短路径"></a>单源点最短路径</h4><h5 id="dijiesira算法"><a href="#dijiesira算法" class="headerlink" title="dijiesira算法"></a>dijiesira算法</h5><p><strong>基本思想</strong><br>    从图的给定源点到其它各个顶点之间客观上应存在一条最短路径，在这组最短路径中，按其长度的递增次序，依次求出到不同顶点的最短路径和路径长度。即按长度递增的次序生成各顶点的最短路径，即<strong>先求出长度最小的一条最短路径</strong>，然后求出长度第二小的最短路径，依此类推，直到求出长度最长的最短路径。<br><strong>算法步骤</strong></p>
<ol>
<li>输入各个点及各点连接边的权重，<strong>创建图</strong>（一开始不知道要创建图，后来想想，要是不创图怎么直到每个点间的连通性，怎么更新vest数组）</li>
<li>创建一个专门用来存储源点到各个点之间距离的数组vest[vertexs]，用getweght方法获得源点与各点间的权重，不连通的点赋值为Max_Value</li>
<li>选取 被选取的点中 挑选相邻的没有被选过的点中 权重最小的一条边，将新选中的点标记为已被操作过，更新各个点之间距离的数组vest</li>
<li>循环执行步骤三，直到所有点都被操作过<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div><div class="line">73</div><div class="line">74</div><div class="line">75</div><div class="line">76</div><div class="line">77</div><div class="line">78</div><div class="line">79</div><div class="line">80</div><div class="line">81</div><div class="line">82</div><div class="line">83</div><div class="line">84</div><div class="line">85</div><div class="line">86</div><div class="line">87</div><div class="line">88</div><div class="line">89</div><div class="line">90</div><div class="line">91</div><div class="line">92</div><div class="line">93</div><div class="line">94</div><div class="line">95</div><div class="line">96</div><div class="line">97</div><div class="line">98</div><div class="line">99</div><div class="line">100</div><div class="line">101</div><div class="line">102</div><div class="line">103</div><div class="line">104</div><div class="line">105</div><div class="line">106</div><div class="line">107</div><div class="line">108</div><div class="line">109</div><div class="line">110</div><div class="line">111</div><div class="line">112</div><div class="line">113</div><div class="line">114</div><div class="line">115</div><div class="line">116</div><div class="line">117</div><div class="line">118</div><div class="line">119</div><div class="line">120</div><div class="line">121</div><div class="line">122</div><div class="line">123</div><div class="line">124</div><div class="line">125</div><div class="line">126</div><div class="line">127</div><div class="line">128</div><div class="line">129</div><div class="line">130</div><div class="line">131</div><div class="line">132</div><div class="line">133</div><div class="line">134</div><div class="line">135</div><div class="line">136</div><div class="line">137</div><div class="line">138</div><div class="line">139</div><div class="line">140</div><div class="line">141</div><div class="line">142</div><div class="line">143</div><div class="line">144</div><div class="line">145</div><div class="line">146</div><div class="line">147</div><div class="line">148</div><div class="line">149</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">package</span> ACM;</div><div class="line"></div><div class="line"><span class="keyword">import</span> java.util.Scanner;</div><div class="line"><span class="comment">/*</span></div><div class="line"><span class="comment">|Dijkstra算法|</span></div><div class="line"><span class="comment">|适用于边权为正的有向图或者无向图|</span></div><div class="line"><span class="comment">|求从单个源点出发，到所有节点的最短路|</span></div><div class="line"><span class="comment">|优化版：时间复杂度 O(elbn)|</span></div><div class="line"><span class="comment"></span></div><div class="line"><span class="comment">*/</span></div><div class="line"></div><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Dijkstra</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span>[] path;</div><div class="line">    <span class="keyword">int</span>[] dist;</div><div class="line">    VNode Varr[];</div><div class="line">    <span class="keyword">int</span> vertex,edges;</div><div class="line">    <span class="keyword">final</span> <span class="keyword">int</span> INF=Integer.MAX_VALUE;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Dijkstra</span><span class="params">()</span></span>&#123;</div><div class="line">        </div><div class="line">            Scanner sc=<span class="keyword">new</span> Scanner(System.in);</div><div class="line">            vertex=sc.nextInt();edges=sc.nextInt();</div><div class="line">            Varr=<span class="keyword">new</span> VNode[vertex];</div><div class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;vertex;i++)&#123;</div><div class="line">                Varr[i]=<span class="keyword">new</span> VNode();</div><div class="line">                Varr[i].mark=<span class="keyword">false</span>;</div><div class="line">            &#125;</div><div class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;edges;i++)&#123;</div><div class="line">                <span class="keyword">int</span> p1=sc.nextInt(),p2=sc.nextInt(),weight=sc.nextInt();</div><div class="line">                createGraph(p1,p2, weight);</div><div class="line">            &#125;</div><div class="line">            dist=<span class="keyword">new</span> <span class="keyword">int</span>[vertex];</div><div class="line">            path=<span class="keyword">new</span> <span class="keyword">int</span>[vertex];</div><div class="line">            </div><div class="line">            dijkstra(<span class="number">0</span>);</div><div class="line"></div><div class="line">        </div><div class="line">        &#125;</div><div class="line">    </div><div class="line">    <span class="function"><span class="keyword">public</span>  <span class="keyword">void</span>   <span class="title">dijkstra</span><span class="params">(<span class="keyword">int</span> start)</span> </span>&#123;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;vertex;i++)&#123;<span class="comment">//初始化dist和path数组</span></div><div class="line">            dist[i]=getWeight(start,i);</div><div class="line">            </div><div class="line">            path[i]=(i!=start &amp;&amp; dist[i]&lt;INF)?start:-<span class="number">1</span>;</div><div class="line">        &#125;</div><div class="line">        </div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=(start+<span class="number">1</span>)%vertex;i!=start;i=(i+<span class="number">1</span>)%vertex)&#123;<span class="comment">//每次都跳过start算其他顶点</span></div><div class="line">            <span class="keyword">int</span> mindist=INF,min=<span class="number">0</span>;</div><div class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> k=<span class="number">0</span>;k&lt;vertex;k++)&#123;<span class="comment">//每次找start点与其他点权重最小的那条边</span></div><div class="line">                <span class="keyword">if</span> (!Varr[k].mark &amp;&amp; dist[k]&lt;mindist) &#123;</div><div class="line">                    mindist=dist[k];    <span class="comment">//路径长度最小值</span></div><div class="line">                    min=k;              <span class="comment">//路径长度最小值下标</span></div><div class="line">                &#125;           </div><div class="line">            &#125;</div><div class="line">                <span class="keyword">if</span>(mindist==INF)<span class="keyword">break</span>;<span class="comment">//若为无穷大，则说明此点与start无连通图</span></div><div class="line">                Varr[min].mark=<span class="keyword">true</span>;</div><div class="line">            </div><div class="line">                <span class="keyword">for</span>(<span class="keyword">int</span> k=<span class="number">0</span>;k&lt;vertex;k++)&#123;</div><div class="line">                    <span class="comment">//能够被更新的条件有：与min点之间连通、（k,min)间的权重+（start，k)间的权重比(start,min)的权重小、这个点没有在点集中</span></div><div class="line">                    </div><div class="line">                    <span class="keyword">if</span>(!Varr[k].mark &amp;&amp; getWeight(k, min)&lt;INF &amp;&amp; getWeight(k, min)+dist[min]&lt;dist[k])&#123;</div><div class="line"><span class="comment">//                      System.out.println(  getWeight(k, min)+dist[min]+" "+dist[k]);</span></div><div class="line">                        dist[k]=getWeight(k, min)+dist[min]; path[k]=min;</div><div class="line">                    &#125;</div><div class="line">                    </div><div class="line">                &#125;</div><div class="line">            &#125;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;vertex;i++)&#123;</div><div class="line">            <span class="keyword">if</span>(i==start)</div><div class="line">                System.out.println(start+<span class="string">"-&gt;"</span>+start+<span class="string">":"</span>+<span class="number">0</span>);</div><div class="line">            <span class="keyword">else</span> <span class="keyword">if</span>(dist[i]==INF)&#123;</div><div class="line">                System.out.println(start+<span class="string">"-&gt;"</span>+i+<span class="string">":"</span>+(-<span class="number">1</span>));</div><div class="line">            &#125;<span class="keyword">else</span>&#123;</div><div class="line">                System.out.println(start+<span class="string">"-&gt;"</span>+i+<span class="string">":"</span>+dist[i]);</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">        </div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">getWeight</span><span class="params">(<span class="keyword">int</span> start, <span class="keyword">int</span> end)</span> </span>&#123;</div><div class="line"></div><div class="line">        <span class="keyword">boolean</span> []mark=<span class="keyword">new</span> <span class="keyword">boolean</span>[vertex];</div><div class="line">        <span class="keyword">if</span> (start==end)</div><div class="line">            <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line"></div><div class="line">        ENode node = Varr[start].firstEdge;</div><div class="line"><span class="comment">//        System.out.println(node);</span></div><div class="line">        <span class="keyword">while</span> (node!=<span class="keyword">null</span>) &#123;</div><div class="line">            </div><div class="line">            <span class="keyword">if</span> (end==node.ivex)</div><div class="line">                <span class="keyword">return</span> node.weight;</div><div class="line">            </div><div class="line">            node = node.nextEdge;</div><div class="line">           </div><div class="line">        &#125;</div><div class="line">        <span class="keyword">return</span> INF;</div><div class="line">    &#125;</div><div class="line">        </div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">createGraph</span><span class="params">(<span class="keyword">int</span> p1,<span class="keyword">int</span> p2,<span class="keyword">int</span> weight)</span></span>&#123;<span class="comment">//创建图</span></div><div class="line">        </div><div class="line">        ENode e1=<span class="keyword">new</span> ENode(p2, weight);</div><div class="line">       </div><div class="line">                  Linklast(Varr[p1].firstEdge, e1);<span class="comment">// 将node链接到"p1所在链表的末尾"</span></div><div class="line">       </div><div class="line">        ENode e2=<span class="keyword">new</span> ENode(p1, weight);</div><div class="line">        </div><div class="line">                  Linklast(Varr[p2].firstEdge, e2);<span class="comment">// 将node链接到"p2所在链表的末尾"</span></div><div class="line">    &#125;</div><div class="line">    </div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">Linklast</span><span class="params">(ENode list ,ENode enode)</span></span>&#123;</div><div class="line">        <span class="keyword">if</span>(list==<span class="keyword">null</span>)list=enode;</div><div class="line">        <span class="keyword">else</span> &#123;</div><div class="line">            ENode e=list;       </div><div class="line">            <span class="keyword">while</span> (e.nextEdge!=<span class="keyword">null</span>) e=e.nextEdge;</div><div class="line">            e.nextEdge=enode;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    </div><div class="line">    </div><div class="line">    </div><div class="line"> <span class="class"><span class="keyword">class</span> <span class="title">VNode</span> </span>&#123;</div><div class="line">        <span class="keyword">int</span> data;          <span class="comment">// 顶点信息</span></div><div class="line">        ENode firstEdge;    <span class="comment">// 指向第一条依附该顶点的弧</span></div><div class="line">        <span class="keyword">boolean</span> mark=<span class="keyword">false</span>; <span class="comment">//用来判断是否被选中</span></div><div class="line">        <span class="function"><span class="keyword">public</span> <span class="title">VNode</span><span class="params">(<span class="keyword">int</span> data)</span> </span>&#123;</div><div class="line">            <span class="keyword">super</span>();</div><div class="line">            <span class="keyword">this</span>.data = data;</div><div class="line">            mark=<span class="keyword">false</span>;</div><div class="line">        &#125;</div><div class="line">        <span class="function"><span class="keyword">public</span> <span class="title">VNode</span><span class="params">()</span> </span>&#123;</div><div class="line">            <span class="keyword">super</span>();</div><div class="line">            mark=<span class="keyword">false</span>;</div><div class="line">        &#125;</div><div class="line">        </div><div class="line">    &#125;</div><div class="line">    </div><div class="line">     <span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">ENode</span> </span>&#123;</div><div class="line">            <span class="keyword">int</span> ivex;       <span class="comment">// 该边所指向的顶点的位置</span></div><div class="line">            <span class="keyword">int</span> weight;     <span class="comment">// 该边的权</span></div><div class="line">            ENode nextEdge; <span class="comment">// 指向下一条弧的指针(其他与该顶点邻接的弧)</span></div><div class="line">            <span class="function"><span class="keyword">public</span> <span class="title">ENode</span><span class="params">(<span class="keyword">int</span> ivex, <span class="keyword">int</span> weight)</span> </span>&#123;</div><div class="line">                <span class="keyword">super</span>();</div><div class="line">                <span class="keyword">this</span>.ivex = ivex;</div><div class="line">                <span class="keyword">this</span>.weight = weight;</div><div class="line">            &#125;</div><div class="line">            </div><div class="line">    &#125;</div><div class="line">     <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</div><div class="line">        Dijkstra dijkstra=<span class="keyword">new</span> Dijkstra();</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
</li>
</ol>
<h4 id="每一对顶点间的最短路径"><a href="#每一对顶点间的最短路径" class="headerlink" title="每一对顶点间的最短路径"></a>每一对顶点间的最短路径</h4><h5 id="floyed算法"><a href="#floyed算法" class="headerlink" title="floyed算法"></a>floyed算法</h5><p><img src="http://note.youdao.com/yws/res/1402/WEBRESOURCEff37f8fc3caf57bbd159cba23b5fc09a" alt="Alt text"><br><img src="http://note.youdao.com/yws/res/1405/WEBRESOURCE90a6bb7a362c0b5320f02be0db19729d" alt="Alt text"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">package</span> ACM;</div><div class="line"></div><div class="line">    <span class="keyword">import</span> java.util.Scanner;</div><div class="line">    <span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Floyd</span> </span>&#123;</div><div class="line"></div><div class="line">    <span class="keyword">int</span> [][]dis;</div><div class="line"></div><div class="line">    <span class="keyword">int</span> vertexs,edges;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Floyd</span><span class="params">()</span> </span>&#123;</div><div class="line"></div><div class="line"></div><div class="line">    Scanner sc=<span class="keyword">new</span> Scanner(System.in);</div><div class="line"></div><div class="line">    vertexs=sc.nextInt();</div><div class="line"></div><div class="line">    edges=sc.nextInt();</div><div class="line"></div><div class="line">    dis=<span class="keyword">new</span> <span class="keyword">int</span>[vertexs][vertexs];</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; vertexs; i++) </div><div class="line"></div><div class="line"></div><div class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; vertexs; j++) </div><div class="line"></div><div class="line"></div><div class="line">                 dis[i][j] =Integer.MAX_VALUE;<span class="comment">//初始化dis数组为无穷大，如果后面没有路径到达，就是无穷大</span></div><div class="line"></div><div class="line"></div><div class="line"></div><div class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;edges;i++)&#123;</div><div class="line"></div><div class="line"></div><div class="line">    <span class="keyword">int</span> p1=sc.nextInt(),p2=sc.nextInt(),weight=sc.nextInt();</div><div class="line"></div><div class="line"></div><div class="line">    dis[p1][p2]=weight;dis[p2][p1]=weight;</div><div class="line"></div><div class="line"></div><div class="line">    &#125;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> k = <span class="number">0</span>; k &lt; vertexs; k++) </div><div class="line"></div><div class="line"></div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; vertexs; i++) </div><div class="line"></div><div class="line"></div><div class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; vertexs; j++) </div><div class="line"></div><div class="line"></div><div class="line">                <span class="comment">//每次都选最小</span></div><div class="line"></div><div class="line"></div><div class="line">                dis[i][j] = dis[i][j]&lt;(dis[i][k] + dis[k][j])?dis[i][j]:(dis[i][k] + dis[k][j]);  </div><div class="line"></div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</div><div class="line"></div><div class="line"></div><div class="line">    <span class="comment">// TODO Auto-generated method stub</span></div><div class="line"></div><div class="line">    &#125;</div><div class="line"></div><div class="line">    &#125;</div></pre></td></tr></table></figure>
<h5 id="SPFA算法"><a href="#SPFA算法" class="headerlink" title="SPFA算法"></a>SPFA算法</h5><p><strong>spfa算法功能</strong>：给定一个加权连通图，选取一个顶点，称为起点，求取起点到其它所有顶点之间的最短距离，其显著特点是可以求含负权图的单源最短路径，且效率较高。（PS：引用自百度百科：spfa是求单源最短路径的一种算法，它还有一个重要的功能是判负环（在差分约束系统中会得以体现），在Bellman-ford算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。）<br><strong>spfa算法思想</strong>：spfa就是BellmanFord的一种实现方式，其具体不同在于，对于处理松弛操作时，采用了队列（先进先出方式）操作，从而大大提高了时间复杂度。<br><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">package</span> ACM;</div><div class="line"><span class="keyword">import</span> java.util.ArrayList;</div><div class="line"><span class="comment">/*</span></div><div class="line"><span class="comment"> * spfa算法功能：给定一个加权连通图，选取一个顶点，称为起点，</span></div><div class="line"><span class="comment"> * 求取起点到其它所有顶点之间的最短距离，其显著特点是可以求含负权图的单源最短路径，且效率较高。</span></div><div class="line"><span class="comment"> * （PS：引用自百度百科：spfa是求单源最短路径的一种算法，它还有一个重要的功能是判负环</span></div><div class="line"><span class="comment"> * （在差分约束系统中会得以体现），在Bellman-ford算法的基础上加上一个队列优化</span></div><div class="line"><span class="comment"> * ，减少了冗余的松弛操作，是一种高效的最短路算法。）</span></div><div class="line"><span class="comment"> * spfa算法思想：spfa就是BellmanFord的一种实现方式，其具体不同在于，</span></div><div class="line"><span class="comment"> * 对于处理松弛操作时，采用了队列（先进先出方式）操作，从而大大提高了时间复杂度。</span></div><div class="line"><span class="comment"> */</span></div><div class="line"></div><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">SPFA</span> </span>&#123;</div><div class="line">    <span class="keyword">long</span>[] result;</div><div class="line">    ArrayList&lt;Integer&gt; list ;</div><div class="line">    <span class="keyword">int</span> vertex,edges;</div><div class="line">    <span class="keyword">final</span> <span class="keyword">int</span>  INF=Integer.MAX_VALUE;</div><div class="line">    </div><div class="line">    <span class="class"><span class="keyword">class</span> <span class="title">edge</span></span>&#123;</div><div class="line">        <span class="keyword">int</span> u;</div><div class="line">        <span class="keyword">int</span> v;</div><div class="line">        <span class="keyword">int</span> weight;</div><div class="line">        <span class="function"><span class="keyword">public</span> <span class="title">edge</span><span class="params">(<span class="keyword">int</span> u, <span class="keyword">int</span> v, <span class="keyword">int</span> weight)</span> </span>&#123;</div><div class="line">            <span class="keyword">super</span>();</div><div class="line">            <span class="keyword">this</span>.u = u;</div><div class="line">            <span class="keyword">this</span>.v = v;</div><div class="line">            <span class="keyword">this</span>.weight = weight;</div><div class="line">        &#125;</div><div class="line">        </div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">spfa</span><span class="params">()</span> </span>&#123;</div><div class="line">         list = <span class="keyword">new</span> ArrayList&lt;Integer&gt;();</div><div class="line">            result = <span class="keyword">new</span> <span class="keyword">long</span>[vertex];</div><div class="line">            <span class="keyword">int</span> s=<span class="number">0</span>;<span class="comment">//出发的点；</span></div><div class="line">            <span class="keyword">boolean</span>[] used = <span class="keyword">new</span> <span class="keyword">boolean</span>[vertex];</div><div class="line">            <span class="keyword">int</span>[] num = <span class="keyword">new</span> <span class="keyword">int</span>[vertex];</div><div class="line">            edge[] A=<span class="keyword">new</span> edge[edges];</div><div class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>;i &lt; vertex;i++) &#123;</div><div class="line">                result[i] = INF;</div><div class="line">                used[i] = <span class="keyword">false</span>;</div><div class="line">            &#125;</div><div class="line">            </div><div class="line">            result[s] = <span class="number">0</span>;     <span class="comment">//第s个顶点到自身距离为0</span></div><div class="line">            used[s] = <span class="keyword">true</span>;    <span class="comment">//表示第s个顶点进入数组队</span></div><div class="line">            num[s] = <span class="number">1</span>;       <span class="comment">//表示第s个顶点已被遍历一次</span></div><div class="line">            list.add(s);      <span class="comment">//第s个顶点入队</span></div><div class="line">            <span class="keyword">while</span> (list.size()!=<span class="number">0</span>) &#123;</div><div class="line">                <span class="keyword">int</span> a = list.get(<span class="number">0</span>);</div><div class="line">                list.remove(<span class="number">0</span>);</div><div class="line">                <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>;i &lt; A.length;i++) &#123;</div><div class="line">                    <span class="keyword">if</span>(a==A[i].u &amp;&amp; result[A[i].v] &gt; result[A[i].u]+A[i].weight)</div><div class="line">                        result[A[i].v] =result[A[i].u]+A[i].weight;</div><div class="line">                    <span class="keyword">if</span>(!used[A[i].v])&#123;</div><div class="line">                        list.add(A[i].v);</div><div class="line">                        num[A[i].v]++;</div><div class="line">                        <span class="keyword">if</span> (num[A[i].v]&gt;vertex) <span class="comment">//判断是否成环</span></div><div class="line">                            <span class="keyword">return</span> <span class="keyword">false</span>;<span class="comment">//</span></div><div class="line">                        used[A[i].v] = <span class="keyword">true</span>;   <span class="comment">//表示边A[i]的终点b已进入数组队</span></div><div class="line">                    &#125;</div><div class="line">                &#125;</div><div class="line">                used[a]=<span class="keyword">false</span>;<span class="comment">//顶点a出数组对</span></div><div class="line">            &#125;</div><div class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</div><div class="line">    &#125;</div><div class="line">    </div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</div><div class="line">        <span class="comment">// TODO Auto-generated method stub</span></div><div class="line"></div><div class="line">    &#125;</div><div class="line">    </div><div class="line"></div><div class="line">&#125;</div></pre></td></tr></table></figure></p>

      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/blog/tags/数据结构/" rel="tag"># 数据结构</a>
          
            <a href="/blog/tags/读书笔记/" rel="tag"># 读书笔记</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/blog/2017/10/26/effective java note/" rel="next" title="effective java笔记">
                <i class="fa fa-chevron-left"></i> effective java笔记
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/blog/2017/12/25/队列与栈/" rel="prev" title="栈和队列">
                栈和队列 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          
  <div class="comments" id="comments">
    
      <!--PC版-->
<div id="SOHUCS" ></div>


    

  </div>
     <div class="comments" id="comments">
       
     </div>
   





        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap" >
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
          <img class="site-author-image" itemprop="image"
               src="/blog/images/avatar.gif"
               alt="choichumgming" />
          <p class="site-author-name" itemprop="name">choichumgming</p>
           
              <p class="site-description motion-element" itemprop="description"></p>
          
        </div>
        <nav class="site-state motion-element">

          
            <div class="site-state-item site-state-posts">
              <a href="/blog/archives/">
                <span class="site-state-item-count">15</span>
                <span class="site-state-item-name">日志</span>
              </a>
            </div>
          

          
            
            
            <div class="site-state-item site-state-categories">
              <a href="/blog/categories/index.html">
                <span class="site-state-item-count">5</span>
                <span class="site-state-item-name">分类</span>
              </a>
            </div>
          

          
            
            
            <div class="site-state-item site-state-tags">
              
                <span class="site-state-item-count">6</span>
                <span class="site-state-item-name">标签</span>
              
            </div>
          

        </nav>

        

        <div class="links-of-author motion-element">
          
            
              <span class="links-of-author-item">
                <a href="http://www.weibo.com/u/2558763801" target="_blank" title="微博">
                  
                    <i class="fa fa-fw fa-weibo"></i>
                  
                    
                      微博
                    
                </a>
              </span>
            
          
        </div>

        
        

        
        

        


      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#图的基本概念"><span class="nav-number">1.</span> <span class="nav-text">图的基本概念</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#图的定义和术语"><span class="nav-number">1.1.</span> <span class="nav-text">图的定义和术语</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#完全无向图"><span class="nav-number">1.2.</span> <span class="nav-text">完全无向图</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#邻接链表法"><span class="nav-number">1.3.</span> <span class="nav-text">邻接链表法</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#图的连通性问题"><span class="nav-number">2.</span> <span class="nav-text">图的连通性问题</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#无向图的连通分量和生成树"><span class="nav-number">2.1.</span> <span class="nav-text">无向图的连通分量和生成树</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#最小生成树"><span class="nav-number">2.2.</span> <span class="nav-text">最小生成树</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#普里姆-Prim-算法"><span class="nav-number">2.2.1.</span> <span class="nav-text">普里姆(Prim)算法</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#克鲁斯卡尔-Kruskal-算法"><span class="nav-number">2.3.</span> <span class="nav-text">克鲁斯卡尔(Kruskal)算法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#最短路径"><span class="nav-number">2.4.</span> <span class="nav-text">最短路径</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#单源点最短路径"><span class="nav-number">2.4.1.</span> <span class="nav-text">单源点最短路径</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#dijiesira算法"><span class="nav-number">2.4.1.1.</span> <span class="nav-text">dijiesira算法</span></a></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#每一对顶点间的最短路径"><span class="nav-number">2.4.2.</span> <span class="nav-text">每一对顶点间的最短路径</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#floyed算法"><span class="nav-number">2.4.2.1.</span> <span class="nav-text">floyed算法</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#SPFA算法"><span class="nav-number">2.4.2.2.</span> <span class="nav-text">SPFA算法</span></a></li></ol></li></ol></li></ol></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright" >
  
  &copy; 
  <span itemprop="copyrightYear">2018</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">choichumgming</span>

  
</div>


  <div class="powered-by">
    由 <a class="theme-link" href="https://hexo.io">Hexo</a> 强力驱动
  </div>

  <span class="post-meta-divider">|</span>

  <div class="theme-info">
    主题 &mdash;
    <a class="theme-link" href="https://github.com/iissnan/hexo-theme-next">
      NexT.Gemini
    </a>
  </div>


        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  <script type="text/javascript" src="/blog/lib/jquery/index.js?v=2.1.3"></script>

  
  <script type="text/javascript" src="/blog/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>

  
  <script type="text/javascript" src="/blog/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>

  
  <script type="text/javascript" src="/blog/lib/velocity/velocity.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/blog/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/blog/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>


  


  <script type="text/javascript" src="/blog/js/src/utils.js?v=5.1.2"></script>

  <script type="text/javascript" src="/blog/js/src/motion.js?v=5.1.2"></script>



  
  


  <script type="text/javascript" src="/blog/js/src/affix.js?v=5.1.2"></script>

  <script type="text/javascript" src="/blog/js/src/schemes/pisces.js?v=5.1.2"></script>



  
  <script type="text/javascript" src="/blog/js/src/scrollspy.js?v=5.1.2"></script>
<script type="text/javascript" src="/blog/js/src/post-details.js?v=5.1.2"></script>



  


  <script type="text/javascript" src="/blog/js/src/bootstrap.js?v=5.1.2"></script>



  


  




	





  





  




  
    <script type="text/javascript">
    (function(){
      var appid = 'cytnT5dky';
      var conf = '56c170b7352bd027682e3707e9eb5071';
      var width = window.innerWidth || document.documentElement.clientWidth;
      if (width < 960) {
      window.document.write('<script id="changyan_mobile_js" charset="utf-8" type="text/javascript" src="https://changyan.sohu.com/upload/mobile/wap-js/changyan_mobile.js?client_id=' + appid + '&conf=' + conf + '"><\/script>'); } else { var loadJs=function(d,a){var c=document.getElementsByTagName("head")[0]||document.head||document.documentElement;var b=document.createElement("script");b.setAttribute("type","text/javascript");b.setAttribute("charset","UTF-8");b.setAttribute("src",d);if(typeof a==="function"){if(window.attachEvent){b.onreadystatechange=function(){var e=b.readyState;if(e==="loaded"||e==="complete"){b.onreadystatechange=null;a()}}}else{b.onload=a}}c.appendChild(b)};loadJs("https://changyan.sohu.com/upload/changyan.js",function(){
        window.changyan.api.config({appid:appid,conf:conf})});
      }
    })();
    </script>
    <script type="text/javascript" src="https://assets.changyan.sohu.com/upload/plugins/plugins.count.js"></script>
  





  





  

  

  

  

  

  

</body>
</html>
